/*
  User: Yemao Luo
  Date: 2021/10/29
  Time: 13:56
*/

import java.util.ArrayList;
import java.util.Random;

public class Class07HW {
    public static void main(String[] args) {
        ArrayList<Integer> sample = new ArrayList<>();
        Method method = new Method();
        Random random = new Random();
        for (int i = 0; i < 15; i++) {
            sample.add(random.nextInt(100));
        }
        System.out.println("待排数组：" + sample);
        System.out.println("--------------------");
        System.out.println("冒泡排序：" + method.bubbleSort(sample));
        System.out.println("--------------------");
        System.out.println("选择排序：" + method.selectSort(sample));
        System.out.println("--------------------");
        System.out.println("插入排序：" + method.insertionSort(sample));
        System.out.println("--------------------");
        System.out.println("快速排序：" + method.quickSort(sample));
        System.out.println("--------------------");
        System.out.println("希尔排序：" + method.hillSort(sample));
        System.out.println("--------------------");
        System.out.println("并归排序：" + method.mergeSort(sample));
    }
}

class Method {
    public ArrayList<Integer> sort(ArrayList<Integer> sample, int low, int high) {
        int i, j, index;
        if (low > high) {
            return sample;
        }
        i = low;
        j = high;
        index = sample.get(i);
        while (i < j) {
            while (i < j && sample.get(j) >= index)
                j--;
            if (i < j)
                sample.set(i++, sample.get(j));
            while (i < j && sample.get(i) < index)
                i++;
            if (i < j)
                sample.set(j--, sample.get(i));
        }
        sample.set(i, index);
        sort(sample, low, i - 1);
        sort(sample, i + 1, high);
    }

    public ArrayList<Integer> quickSort(ArrayList<Integer> a) {
        return sort(a, 0, a.size() - 1);
    }

    public ArrayList<Integer> hillSort(ArrayList<Integer> sample) {
        int gap = sample.size() / 2;
        ArrayList<Integer> sorted = new ArrayList();
        while (gap > 0) {
            for (int i = 0; i < gap; i++) {
                for (int j = 0; j < sample.size(); j++) {
                    if ((j + gap) > sample.size() - 1) {
                        break;
                    }
                    if (sample.get(j + gap) < sample.get(j)) {
                        int tem = sample.get(j);
                        sample.set(j, sample.get(j + gap));
                        sample.set((j + gap), tem);
                    }
                }
            }
            gap /= 2;
        }
        return sample;
    }

    public ArrayList<Integer> insertionSort(ArrayList<Integer> sample_s) {
        ArrayList<Integer> sorted = new ArrayList<>();
        ArrayList<Integer> sample = new ArrayList<>();
        for (int i = 0; i < sample_s.size(); i++) {
            sample.add(sample_s.get(i));
        }
        sorted.add(sample.get(0));
        sample.remove(0);
        Boolean flag;
        for (int i = 0; i < sample.size(); i++) {
            flag = true;
            int tem = sample.get(i);
            for (int j = 0; j < sorted.size(); j++) {
                if (tem <= sorted.get(j)) {
                    sorted.add(j, tem);
                    flag = false;
                    break;
                }
            }
            if (flag) {
                sorted.add(tem);
            }
        }
        return sorted;
    }

    public ArrayList<Integer> selectSort(ArrayList<Integer> sample) {
        for (int i = 0; i < sample.size() - 1; i++) {
            int min = i;
            for (int j = i + 1; j < sample.size(); j++) {
                if (sample.get(j) < sample.get(min)) {
                    min = j;
                }
            }
            if (i != min) {
                int temp = sample.get(i);
                sample.set(i, sample.get(min));
                sample.set(min, temp);
            }
        }
        return sample;
    }

    public ArrayList<Integer> bubbleSort(ArrayList<Integer> sample) {
        for (int i = 0; i < sample.size() - 1; i++) {
            for (int j = 0; j < sample.size() - 1; j++) {
                if (sample.get(j + 1) < sample.get(j)) {
                    int temp = sample.get(j);
                    sample.set(j, sample.get(j + 1));
                    sample.set(j + 1, temp);
                }
            }
        }
        return sample;
    }

    public ArrayList<Integer> mergeSort(ArrayList<Integer> sample) {
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        int center;
        if (sample.size() == 1) {
            return sample;
        } else {
            center = sample.size() / 2;
            for (int i = 0; i < center; i++) {
                left.add(sample.get(i));
            }
            for (int i = center; i < sample.size(); i++) {
                right.add(sample.get(i));
            }
            left = mergeSort(left);
            right = mergeSort(right);
            merge(left, right, sample);
        }
        return sample;
    }

    public void merge(ArrayList<Integer> left, ArrayList<Integer> right, ArrayList<Integer> sample) {
        int leftIndex = 0;
        int rightIndex = 0;
        int sampleIndex = 0;
        while (leftIndex < left.size() && rightIndex < right.size()) {
            if ((left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) {
                sample.set(sampleIndex, left.get(leftIndex));
                leftIndex++;
            } else {
                sample.set(sampleIndex, right.get(rightIndex));
                rightIndex++;
            }
            sampleIndex++;
        }
        ArrayList<Integer> rest;
        int restIndex;
        if (leftIndex >= left.size()) {
            rest = right;
            restIndex = rightIndex;
        } else {
            rest = left;
            restIndex = leftIndex;
        }
        for (int i = restIndex; i < rest.size(); i++) {
            sample.set(sampleIndex, rest.get(i));
            sampleIndex++;
        }
    }
}
